324. Числа

Делать было нечего, дело было вечером... Так как команда у Тимура большая, а бумаги всегда много, занятие было найдено.

Возьмем число a. Возьмем b. И выпишем все числа от a до b. Подсчитайте сумму всех написанных цифр.

Вход. Два натуральных числа a и b (a ≤ b), разделенные пробелом. Числа не превышают 10¹².

Выход. Вывести сумму всех написанных цифр.

Пример входа	Пример выхода
1 10	46

РЕШЕНИЕ

рекурсия

Анализ алгоритма

Пусть функция f(x) вычисляет сумму цифр всех чисел от 0 до x. Тогда ответом задачи будет значение f(b) – f(a – 1). Рассмотрим рекурсивную реализацию функции f(x).

Суммирование цифр чисел от 0 до x = разобьем на две части:

1. суммирование цифр чисел от 0 до ;

2. суммирование цифр чисел от до ;

Рассмотрим первое множество чисел. На последней позиции повторяется последовательность из чисел 0, 1, …, 9 x / 10 раз. Сумма цифр от 0 до 9 равна 45, поэтому сумма единиц в числах первого множества равна x / 10 * 45. Сумма цифр, стоящих на других местах, равна 10 * f(x / 10 – 1).

Сумма цифр в числах второго множества состоит из суммы цифр единиц (0 + 1 + … + a₀) и суммы цифр числа = x /10, умноженного на количество чисел во множестве, то есть на (a₀ + 1). Положим temp = a₀ = x % 10. Пусть sum(x) – функция, вычисляющая сумму цифр числа x. Тогда сумма цифр всех чисел второго множества равна

(temp + 1) * sum(x / 10) + temp * (temp + 1) / 2

Реализация алгоритма

Функция sum вычисляет сумму цифр числа x.

long long sum (long long x)

{

return (x <= 0) ? 0 : x % 10 + sum(x / 10);

}

Реализация функции f(x).

long long f(long long x)

{

if (x <= 0) return 0;

long long res = x / 10 * 45;

long long temp = x % 10;

res = res + 10 * f(x / 10 - 1) + (temp + 1) * sum(x / 10) +

temp * (temp + 1) / 2;

return res;

}

Основная часть программы. Читаем входные данные. Вычисляем и выводим ответ.

scanf("%lld %lld",&a,&b);

res = f(b) - f(a - 1);

printf("%lld\n",res);